1146E - Hot is Cold - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000 + 1;

vector <pair <int, int>> num;
int n, q, a[MAXN], laz[MAXN * 4], ans[MAXN], ans2[MAXN];

void inPut() {
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] > 0) {
			num.push_back({a[i], i});
			num.push_back({a[i] * -1, i * -1});
		}
		else {
			num.push_back({a[i], i * -1});
			num.push_back({a[i] * -1, i});
		}
	}
}

void change(int u, int x) {
	if (x == 0)
		return;
	if (x == 1 || x == 2) {
		laz[u] = x;
		return;
	}
	if (laz[u] == 0)
		laz[u] = x;
	else if (laz[u] == 1)
		laz[u] = 2;
	else if (laz[u] == 2)
		laz[u] = 1;
	else
		laz[u] = 0;
}

void push(int u) {
	change(2 * u, laz[u]);
	change(2 * u + 1, laz[u]);
	laz[u] = 0;
}

void update(int l, int r, int u, int l2, int r2, int x) {
	if (r <= l2 || l >= r2)
		return;
	if (l >= l2 && r <= r2) {
		change(u, x);
		return;
	}
	push(u);
	update(l, (r + l) / 2, 2 * u, l2, r2, x);
	update((r + l) / 2, r, 2 * u + 1, l2, r2, x);
}

void makeLess(int u) {
	pair <int, int> v3 = {u, -1}; 
	if (u < 0)
		v3.second = -1 * 2 * n;
	int v = lower_bound(num.begin(), num.end(), v3) - num.begin();
	if (v == 0)
		return;
	if (v <= n) {
		update(0, 2 * n, 1, 0, v, 1);
		update(0, 2 * n, 1, 2 * n - v, 2 * n, 2);
		return;
	}
	int v2 = n - (v - n);
	update(0, 2 * n, 1, 0, v2, 1);
	update(0, 2 * n, 1, v, 2 * n, 2);
	update(0, 2 * n, 1, v2, v, 3);
}

void makeBiger(int u) {
	pair <int, int> v3 = {u, 1};
	if (u > 0)
		v3.second = 2 * n;
	int v = upper_bound(num.begin(), num.end(), v3) - num.begin();
	if (2 * n - v == 0)
		return;
	if (v >= n) {
		update(0, 2 * n, 1, v, 2 * n, 1);
		update(0, 2 * n, 1, 0, 2 * n - v, 2);
		return;
	}
	int v2 = n - v;
	update(0, 2 * n, 1, v2 + n, 2 * n, 1);
	update(0, 2 * n, 1, 0, v, 2);
	update(0, 2 * n, 1, v, n + v2, 3);
}

void coutAll(int l, int r, int u) {
	cout << l << " " << r << " " << laz[u] << endl;
	if (r - l == 1) 
		return;
	coutAll(l, (r + l) / 2, 2 * u);
	coutAll((r + l) / 2, r, 2 * u + 1);
}

void makeQue() {
	for (int i = 0; i < q; i++) {
		char x;
		int y;
		cin >> x >> y;
		if (x == '<')
			makeLess(y);
		else
			makeBiger(y);
		//cout << "----------------------" << endl;
		//coutAll(0, n * 2, 1);
	}
}

void updateAll(int l, int r, int u) {
	if (r - l == 1) {
		ans[l] = laz[u];
		return;
	}
	push(u);
	updateAll(l, (r + l) / 2, 2 * u);
	updateAll((r + l) / 2, r, 2 * u + 1);
}

void makeAns2() {
	for (int i = 0; i < 2 * n; i++) 
		if (num[i].first != a[max(num[i].second, -1 * num[i].second)]) {
			if (ans[i] == 2 || ans[i] == 3)
				ans2[max(num[i].second, -1 * num[i].second)] = num[i].first;
		}
		else {
			if (ans[i] == 2 || ans[i] == 0)
				ans2[max(num[i].second, -1 * num[i].second)] = num[i].first;
		}
}

int main() {
	inPut();
	sort(num.begin(), num.end());
	makeQue();
	updateAll(0, 2 * n, 1);
	makeAns2();
	for (int i = 0; i < n; i++)
		cout << ans2[i] << " ";
	cout << endl;
}